from typing import List


def coinChange(coins: List[int], amount: int) -> int:
    max_value = 1 << 32
    dp = [max_value for i in range(amount + 1)]
    for i in range(amount + 1):
        if i == 0:
            dp[0] = 0
        else:
            for c in coins:
                if i - c >= 0 and dp[i - c] != max_value:
                    dp[i] = min(dp[i - c] + 1, dp[i])

    return -1 if dp[amount] == max_value else dp[amount]


# dp[i]表示前家能抢到的钱的最大数目
def rob(nums: List[int]) -> int:
    dp = [0 for _ in range(len(nums) + 1)]
    if len(nums) == 1:
        dp[0] = nums[0]
        return dp[0]
    elif len(nums) == 2:
        dp[1] = max(nums)
        return dp[1]
    else:
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
        for i in range(2, len(nums)):
            dp[i] = (max(dp[i - 2] + nums[i], dp[i - 1]))
        return dp[len(nums) - 1]


def maxProfit(prices):
    length = len(prices)
    if length <= 1:
        return 0
    else:
        cache = 0
        int_value = prices[0]
        for index in range(length):
            if prices[index] < int_value:
                int_value = prices[index]
            result = max(cache, prices[index] - int_value)
            cache = result
        return result
